#include <iostream>
#include <cstdlib>
using namespace std;



struct ListNode 
{
	int val;
	ListNode* next;
	ListNode(int x): val(x),next(NULL) {}
};

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){
	ListNode* pResult = NULL;
	bool  bereted =false;
	if( l1 != NULL && l2!= NULL ){
		pResult = new ListNode(l1->val+l2->val);
		if(pResult->val >= 10 ){
			pResult->val %= 10;
			bereted = true;
		}
		pResult->next = addTwoNumbers(l1->next,l2->next);
		if(bereted) { 
			if(pResult->next == NULL )
			{
				pResult->next = new ListNode(1);
			}
			else
			{
				ListNode* temp = pResult->next;
				if(pResult->next->val==9)
				{
					while(temp != NULL)
					{
						if(temp->val == 9)
						{			
							temp->val += 1;
							temp->val %=10;
							if(temp->next == NULL )
							{
								temp->next = new ListNode(1);
								break;
							}
							temp=temp->next;
						}
						else
						{
							temp->val += 1;
							break;
						}
					}
				}
				
				else
				{
					
					pResult->next->val += 1;

				}
				
					
			}
		}
		
	}
	else if(l1!= NULL || l2!=NULL ){
		if(l1){
			pResult = new ListNode(l1->val);
			pResult->next = addTwoNumbers(l1->next,NULL);
		}
		else
		{
			pResult = new ListNode(l2->val);
			pResult->next = addTwoNumbers(NULL,l2->next);
		}
	}
	return pResult;
}


void Cleanup(ListNode* l){
	do 
	{
		ListNode* temp = l;
		if(temp!=NULL)
		{
			l = l->next;
		}
		delete temp;
	} while (l!=NULL);
}




ListNode* addTwoNumbers1(ListNode* l1,ListNode* l2){
	bool bret = false;
	ListNode* result = l1;
	//ListNode* temp = l1;
	ListNode* tmp =l1->next;
	while(l1!=NULL||l2!=NULL){
		if(l1!=NULL && l2!=NULL){
			l1->val += l2->val;
			if(l1->val >= 10){
				bret=true;
				l1->val %= 10;
				if(l1->next) {
					tmp = l1->next;
					l1->next->val += 1;
				}
				else{
					if(l2->next){
						tmp = l2->next;

						l2->next->val += 1;
						l2->next = NULL;
						l1->next = tmp;

					}
					else{
						l1->next = new ListNode(1);
					}
				}
			}
			else{
				if(l1->next) {tmp = l1->next;}
				else{
					if(l2->next){
						tmp = l2->next;
						l2->next = NULL;
						l1->next = tmp;
					}
				}
			}
			l1 = tmp;
			l2 = l2->next;
			
			//curnode = curnode->next;
		}
		else{
			ListNode* temp = tmp;
			while(temp!=NULL){
				if(temp->val == 10 ){
					temp->val %=10;
					if(temp->next==NULL){
						temp->next = new ListNode(1);
						break;
					}
					temp->next->val += 1;
					
				}
				temp = temp->next;
			}
			break;
		}
	}
	//result->next = tmp;
	return result;
}


int main()
{
	ListNode* l1=new ListNode(0);
	/*l1->next = new ListNode(6);
	l1->next->next = new ListNode(3);*/

	ListNode* l2 = new ListNode(9);
	l2->next = new ListNode(9);
	l2->next->next = new ListNode(9);
	/*l2->next->next->next = new ListNode(9);
	l2->next->next->next->next = new ListNode(8);*/


	ListNode* presult = addTwoNumbers1(l1,l2);






	Cleanup(presult);
	Cleanup(l2);
	/*Cleanup(l2);
	Cleanup(l1);*/
	

	return 0;
}